#pragma once
#include<iostream>
#include<cmath>
#include<string>
using namespace std;

#define INFINITYS 65535

int** distances;//记录从源点到终点当前最短路径长度
int row, column, num;//行，列，点的个数
double distancess;//两点之间的距离
char num_dist[20];//距离转换中间量



/*测试用例
0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 9
0 0 5 0 0 6
0 0 0 5 0 0
3 0 0 0 1 0
*/
struct Coor {
	int x;
	int y;
};
struct Node {
	
	char** a;
	
	Coor* coor;
};
typedef struct Graph {
	Node node;//定点表
	
	double** edg;
}Graph;


//查询地址下标
int address(Graph g, char *P) {
	for (int i = 0; i < num; i++) {
		if (strcmp(P, g.node.a[i])==0) {
			return i;
		}
	}
	return 0;
}

void CreateGraph(Graph* g) {
	int i = 0;
	int j = 0;
	
	for (i = 0; i < num; i++)
		for (j = 0; j < num; j++)
			g->edg[i][j] = 0;
}
//设置权重
void SetWeight(Graph* g) {
	int i, j;
	for (i = 0; i < num; i++) {
		for (j = 0; j < num; j++) {
			if (g->edg[i][j] == 0)
				g->edg[i][j] = INFINITYS;
		}
	}
}
//迪杰斯特拉算法
void Dijkstra(Graph g) {
	int VertexNum = num;
	int i, j, k, m, n, t;
	int mini;
	//记录从源点到终点是否已被确定最短路径长度，1表示确定，0表示尚未确定
	int* used = new int[VertexNum];
	
	
	distances = new int* [num];
	for (int j = 0; j < num; j++)
	{
		distances[j] = new int[num];
	}

	SetWeight(&g);
	for (t = 0; t < num; t++)
	{
		for (i = 0; i < VertexNum; i++) {
			used[i] = 0;
			
			distances[t][i] = g.edg[t][i];

		}
		used[t] = 1;
		
		for (i = 0; i < VertexNum; i++) {
			j = 0;
			mini = INFINITYS;
			//计算出最小的
			for (m = 0; m < VertexNum; m++)
			{
				if ((!used[m]) && (distances[t][m] < mini))
				{
					mini = distances[t][m];
					j = m;
				}
			}
			used[j] = 1;
			//在上面基础上继续找点
			//比如上面找到（a,b）
			//下面就找b所能到达的点从而写成（a，b，c）
			for (n = 0; n < VertexNum; n++)
			{
				if ((!used[n]) && (distances[t][n] > distances[t][j] + g.edg[j][n]))
				{
					distances[t][n] = distances[t][j] + g.edg[j][n];
					
				}
			}
		}
	}



	
	
	delete[]used;
}

int dis(Graph g, char* a, char* b)
{
	return distances[address(g, a)][address(g, b)];
}
